#选择排序

**原理**  /*
每一次从待排序的元素中选出最小/最大（排列顺序）的元素，放在已排序好的序列的最后。

example: [4,2,1,3]
第一次循环，找出1的位置，与4交换得到[1,2,4,3]
第二次循环，找出2的位置，不用动
第三次循环，找出3的位置，与4交换得到[1,2,3,4]
*/

**核心**  /*
使用一个min_index来记录除排好序的前缀元素外，当前最小元素的位置，将其放在第i次循环的元素位置vec[i]上
通过控制 [line 27] 来控制升序降序
*/

**我的实现**
vector<int> LySort::selectSort(vector<int>& v) {
    vector<int> out = v;
    // 1. 适当的输入检查
    if (out.size() <= 1)
        return out;
    for (int i = 0; i < out.size(); ++i) {
        // 2. 定义一个变量vec_min_idx，记录第i次选择时的最小元素位置
        int vec_min_idx = i;
        for (int j = i+1; j < out.size(); ++j) {
            // 3. 通过循环寻找当前最小元素的位置，更新到vec_min_idx
            if (out[j] < out[vec_min_idx]) {
                vec_min_idx = j;
            }
        }
        // 4. 将第i次找到的最小值，放在第i个位置vec[i] = vec[vec_min_idx]
        if (i != vec_min_idx)
            std::swap(out[vec_min_idx], out[i]);
    }
    return out;
}


**思考** /*
时间复杂度分析：
第一次内循环(j)比较N-1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。
共比较的次数是 (N - 1) + (N - 2) + ... + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2。
取最高项系数，因此时间复杂度为 O(N^2)

空间复杂度分析：
耗费的空间与输入数据大小无关，无论输入数据增大多少倍，不会耗费额外的空间进行排序（除了数组本身的空间）
因此时间复杂度为 O(1)

稳定性分析：
稳定的关键，在于排序完成后，相同元素的相对顺序是否变化。
但是选择排序没办法保证
example 3[1], 3[2], 3[3], 1
首次交换 1, 3[2], 3[3], 3[1]
可以看到无法保证3个3的原本相对顺序

泛化性分析：
选择排序适合从大量的元素中选择一部分排序元素，例如从10000个元素中选择出大小为前10 的元素就适合用选择排序
*/